class ListNode {
    val: number
    next: ListNode | null
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val === undefined ? 0 : val)
        this.next = (next === undefined ? null : next)
    }
}

/**
 * https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
 * 
 * 求相交链表
 * @param headA 
 * @param headB 
 */
const getIntersectionNode = (headA: ListNode | null, headB: ListNode | null): ListNode | null => {
    // 从头节点开始比较
    let l = headA,
        r = headB;

    // 如果不一样, 就一直往下比较
    while (l !== r) {
        l = l !== null ? l.next : headB;
        r = r !== null ? r.next : headA
    }

    return l
};


const getIntersectionNode3 = (headA: ListNode | null, headB: ListNode | null): ListNode | null => {
    // 两个链表其中有一个为空, 表示没有相交节点
    if (headA === null || headB === null) return null;

    // 两个链表进行拼接 headA 后面拼接 headB, headB后面拼接headA
    let l: ListNode | null = headA,
        r: ListNode | null = headB;

    while (l !== null || r !== null) {
        // 左边为空, l赋值为headB
        if (l == null) l = headB;

        // 右边为空, r赋值为headA
        if (r === null) r = headA;

        // 找到了
        if (l === r) return l

        l = l.next;
        r = r.next;
    }

    // 找不到   
    return null
};


const getIntersectionNode2 = (headA: ListNode | null, headB: ListNode | null): ListNode | null => {
    // 两个链表其中有一个为空, 表示没有相交节点
    if (headA === null || headB === null) return null;

    const dummyHead = new ListNode(0)
    dummyHead.next = headB;

    let l: ListNode | null = headA,
        r: ListNode | null = dummyHead.next;

    while (l !== null) {
        while (r !== null) {
            // 如果不相等
            if (r !== l) r = r.next;
            else {
                return l
            }
        }
        // r重新指向dummyHead.next
        r = dummyHead.next;
        // 往下
        l = l.next;
    }

    // 循环没找到
    return null
};

export {}

// let e = new ListNode(8)
// let four = new ListNode(4)
// let f = new ListNode(5)


// const headA = new ListNode(4);
// headA.next = new ListNode(1)
// headA.next.next = e
// headA.next.next.next = four
// headA.next.next.next.next = f
// console.log(headA)



// const headB = new ListNode(5);
// headB.next = new ListNode(0)
// headB.next.next = new ListNode(1)
// headB.next.next.next = e
// headB.next.next.next.next = four
// headB.next.next.next.next.next = f

// console.log(getIntersectionNode(headA, headB))